package com.gaofeng.algo.kt

import com.sun.org.apache.bcel.internal.generic.NEW
import java.util.*

/**
 * 题目描述
给定一个二维的 0-1 矩阵，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛
屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。
6.2 深度优先搜索 – 25/143 –
输入输出样例
输入是一个二维数组，输出是一个整数，表示最大的岛屿面积。
Input:
[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
Output: 6
最大的岛屿面积为 6，位于最右侧。
 */
fun maxAreaOfIsland(grid: Array<IntArray>): Int {
    if (grid.isEmpty()) {
        return 0
    }
    val m = grid.size
    val n: Int = grid[0].size
    var answer = 0
    val direction = intArrayOf(-1, 0, 1, 0, -1)
    for (i in 0 until m) {
        for (j in 0 until n) {
            var curArea = 0
            val stacki: Deque<Int> = LinkedList()
            val stackj: Deque<Int> = LinkedList()
            stacki.push(i)
            stackj.push(j)
            while (!stacki.isEmpty()) {
                val curri = stacki.pop()
                val currj = stackj.pop()
                if (curri < 0 || currj < 0 || curri == m || currj == n || grid[curri][currj] != 1) {
                    continue
                }
                curArea++
                grid[curri][currj] = 0 //将遍历过的顶点
                //下一步的走向添加到占中
                for (k in 0..4) {
                    val nextI = curri + direction[k]
                    val nextJ = currj + direction[k + 1]
                    stacki.push(nextI)
                    stackj.push(nextJ)
                }
            }
            answer = Math.max(answer, curArea)
        }
    }
    return answer
}

fun findCircleNum(M: Array<IntArray>): Int {
    val size = M.size
    val visited = IntArray(size)
    var count = 0
    for (i in 0 until size) {
        if (visited[i] == 0) {
            dfs(M, visited, i)
            count++
        }
    }
    return count
}

private fun dfs(M: Array<IntArray>, visited: IntArray, i: Int) {
    for (j in M.indices) {
        if (M[i][j] == 1 && visited[j] == 0) {
            visited[j] = 1
            dfs(M, visited, j)
        }
    }
}

var directions = intArrayOf(-1, 0, 1, 0, -1)

fun pacificAtlantic(matrix: Array<IntArray>): List<List<Int>>? {
    val ans: MutableList<List<Int>> = ArrayList()
    val m = matrix.size
    if (m == 0 || matrix[0].isEmpty()) {
        return ans
    }
    val n: Int = matrix[0].size
    val canReachP = Array(m) { BooleanArray(n) }
    val canReachA = Array(m) { BooleanArray(n) }
    for (i in 0 until m) {
        //从左右两边出发
        dfs(matrix, canReachP, i, 0)
        dfs(matrix, canReachA, i, n - 1)
    }
    for (i in 0 until n) {
        //从上下两边出发
        dfs(matrix, canReachP, 0, i)
        dfs(matrix, canReachA, m - 1, i)
    }
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (canReachA[i][j] && canReachP[i][j]) {
                val tempList: MutableList<Int> = ArrayList()
                tempList.add(i)
                tempList.add(j)
                ans.add(tempList)
            }
        }
    }
    return ans
}

private fun dfs(matrix: Array<IntArray>, canReach: Array<BooleanArray>, i: Int, j: Int) {
    if (canReach[i][j]) {
        return
    }
    canReach[i][j] = true
    var x: Int
    var y: Int
    for (k in 0..3) {
        x = i + directions[k]
        y = j + directions[k + 1]
        if (x >= 0 && x < matrix.size && y >= 0 && y < matrix[0].size && matrix[i][j] <= matrix[x][y]) {
            dfs(matrix, canReach, x, y)
        }
    }
}

fun maxAreaOfIsland2(grid: Array<IntArray>): Int {
    if (grid.isEmpty()) {
        return 0
    }
    val m = grid.size
    val n = grid[0].size
    val direction = intArrayOf(-1, 0, 1, 0, -1)
    var maxArea = 0
    for (i in 0 until m) {
        for (j in 0 until n) {
            var area = 0
            val stackI = LinkedList<Int>()
            val stackJ = LinkedList<Int>()
            stackI.push(i)
            stackJ.push(j)
            while (!stackI.isEmpty()) {
                val currentI = stackI.pop()
                val currentJ = stackJ.pop()
                if (currentI < 0 || currentI == m || currentJ < 0 || currentJ == n || grid[currentI][currentJ] != 1) {
                    continue
                }
                grid[currentI][currentJ] = 0
                area++
                for (k in 0 until 4) {
                    val nextI = direction[k]
                    val nextJ = direction[k + 1]
                    stackI.push(nextI)
                    stackJ.push(nextJ)
                }
            }
                maxArea = maxArea.coerceAtLeast(area)
        }
    }
    return maxArea
}